package com.mdnote;

import java.util.Arrays;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/10/11
 * @description
 */
public class QuickSortTemplate {

    public static void main(String[] args) {
        int[] arr = {11, 3, 5, 99, 88, 13, 54, 32};
        quickSort(arr, 0, arr.length - 1);

        System.out.println(Arrays.toString(arr));
    }


    private static void quickSort(int[] arr, int begin, int end) {
        if (begin >= end) {
            return;
        }
        int pivot = partition(arr, begin, end);
        quickSort(arr, begin, pivot - 1);
        quickSort(arr, pivot + 1, end);

    }

    private static int partition(int[] arr, int begin, int end) {
       int pivot = end, counter = begin;
        for (int i = begin; i < end; i++) {
            if (arr[i] < arr[pivot]) {
                int tmp = arr[i]; arr[i] = arr[counter]; arr[counter] = tmp;
                counter++;
            }
        }
        int tmp = arr[counter]; arr[counter] = arr[pivot]; arr[pivot] = tmp;

        return counter;
    }
}
